#include <vector>
#include <algorithm>
#include <iostream>

// 动态规划: 0-1背包问题
/**
 *! @brief  使用贪心算法实现0-1容量问题
 * 
 * @param  weights    物品的重量列表
 * @param  values     物品的价值列表
 * @param  capacity   容器的重量容量
 * 
 * @return int      返回最优解总价值大小
 */

class Item {
public:
    int weight;
    int value;

    // 使用初始化列表
    // Item(int w, int v) : weight(w), value(v) {}
    Item(int weight, int value) {
        this->weight = weight;
        this->value  = value;
    }
};

float capacityKnapSack(const std::vector<int>& weights, 
                    const std::vector<int>& values, 
                    int capacity) {
    std::vector<Item> items;
    for (int i = 0; i < weights.size(); i++) {
         //! 使用emplace_back代替push_back提高性能
        items.emplace_back(weights[i], values[i]);     
    }

    // 定义dp[i][w]:  对于前i个物品，背包容量为w时可以容纳的最大价值为dp[i][w]
    // 最终答案为dp[N][M]
    // N+1 = items.size() + 1
    // M+1 = capacity + 1
    std::vector<std::vector<int>> dp(items.size() + 1, std::vector<int>(capacity + 1, 0));

    //! 如果没有把第i件物品放入背包，那么dp[i][w] = dp[i-1][w]
    //! 如果把第i件物品放入背包，那么dp[i][w]    = val[i-1] + dp[i-1][w-wt[i-1]]
    for (int i = 1; i <= items.size(); i++) {
        for (int w = 1; w <= capacity; w++) {
            if (items[i - 1].weight <= w) {
                // 装入
                int capy = items[i - 1].value + dp[i - 1][w - items[i - 1].weight];
                // 不装入
                int capn = dp[i - 1][w];
                dp[i][w] = std::max(capy, capn);
            } else {
                dp[i][w] = dp[i - 1][w];       // 只能选择不装入
            }
        }
    }

    return dp[items.size()][capacity];
}


int main(int argc, char *argv[]) {
    std::vector<int> weights = {10, 20,  30,  40,  50};
    std::vector<int> values  = {50, 120, 150, 210, 240};

    std::cout << capacityKnapSack(weights, values, 60) << std::endl;

    return 0;
}